package DataStructure.tree;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 从遍历出的序列来还原二叉树
 */
public class RestoreBinaryTree {

    /**
     * 从完全二叉树的层序遍历序列还原
     * 在完全二叉树中，节点从1开始编号，则节点i的左孩子为2i，右孩子为2i+1
     */
    public static TreeNode restoreLevelTraversal(List<Integer> numList) {
        return restoreLevelTraversal(numList, 1);
    }

    /**
     * 递归构造以节点i为根节点的子树，将其左子树设为以2i为根节点的子树，将其右子树设为以2i+1为根节点的子树
     * @param numList 完全二叉树的层序遍历序列
     * @param i 节点i，在序列数组中下标为i-1
     * @return 以节点i为根节点的子树
     */
    private static TreeNode restoreLevelTraversal(List<Integer> numList, int i) {
        if (i > numList.size() || numList.get(i-1) == null) return null;
        TreeNode treeNode = new TreeNode(numList.get(i-1));
        treeNode.left = restoreLevelTraversal(numList, 2*i);
        treeNode.right = restoreLevelTraversal(numList, 2*i+1);
        return treeNode;
    }

    public static TreeNode createTree(String levelOrder) {
        if (levelOrder == null || levelOrder.isEmpty()) {
            return null;
        }
        String[] nodes = levelOrder.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        queue.offer(root);
        for (int i = 1; i < nodes.length; i += 2) {
            TreeNode parent = queue.poll();
            if (!"null".equals(nodes[i])) {
                TreeNode left = new TreeNode(Integer.parseInt(nodes[i]));
                parent.left = left;
                queue.offer(left);
            }
            if (i + 1 < nodes.length && !"null".equals(nodes[i + 1])) {
                TreeNode right = new TreeNode(Integer.parseInt(nodes[i + 1]));
                parent.right = right;
                queue.offer(right);
            }
        }
        return root;
    }
}
